package com.cgwx.commonutils.math;

import com.cgwx.commonutils.struc.Stack;

/**
 * @author GaoWei
 * @Date 2021/8/6 - 10:55
 */
public class ExpressionTree
{
    public static Expression parse(String s) {
        if (s == null) {
            throw new ExpressionParseException("Expression string cannot be null.", -1);
        }
        return build(s, 0);
    }

    private static Expression build(String s, int indexErrorOffset) {
        if (s.trim().length() == 0) {
            return null;
        }
//        堆栈
        Stack s1 = new Stack();
        Stack s2 = new Stack();

        boolean term = true;
        boolean signed = false;
        boolean negate = false;
        for (int i = 0; i < s.length(); i++) {
//            第i位置上的字符的ASCII码 对应的字符
            char c = s.charAt(i);
            if ((c != ' ') && (c != '\t') && (c != '\n')) {
                if (term) {
                    if (c == '(') {
                        if (negate) {
                            throw new ExpressionParseException("Open bracket found after negate.", i);
                        }
                        s2.push("(");
                    }
                    else if ((!signed) && ((c == '+') || (c == '-'))) {
                        signed = true;
                        if (c == '-') {
                            negate = true;
                        }
                    }
                    else if (((c >= '0') && (c <= '9')) || (c == '.')) {
                        int j = i + 1;
                        while (j < s.length()) {
                            c = s.charAt(j);
                            if (((c >= '0') && (c <= '9')) || (c == '.')) {
                                j++;
                            }
                            else {
                                if ((c != 'e') && (c != 'E')) {
                                    break;
                                }
                                j++;
                                if (j < s.length()) {
                                    c = s.charAt(j);
                                    if ((c != '+') && (c != '-') && ((c < '0') || (c > '9'))) {
                                        throw new ExpressionParseException("Expected digit, plus sign or minus sign but found: " + String.valueOf(c), j + indexErrorOffset);
                                    }
                                    j++;
                                }
                                while (j < s.length()) {
                                    c = s.charAt(j);
                                    if ((c < '0') || (c > '9')) {
                                        break;
                                    }
                                    j++;
                                }
                                break;
                            }
                        }
                        double d = 0.0D;
                        String _d = s.substring(i, j);
                        try {
                            d = Double.parseDouble(_d);
                        }
                        catch (Throwable t) {
                            throw new ExpressionParseException("Improperly formatted value: " + _d, i + indexErrorOffset);
                        }
                        if (negate) {
                            d = -d;
                        }
                        s1.push(new ValNode(d));
                        i = j - 1;

                        negate = false;
                        term = false;
                        signed = false;
                    }
                    else if ((c != ',') && (c != ')') && (c != '^') && (c != '*') && (c != '/') && (c != '+') && (c != '-')) {
                        int j = i + 1;
                        while (j < s.length()) {
                            c = s.charAt(j);
                            if ((c == ',') || (c == ' ') || (c == '\t') || (c == '\n') || (c == '(') || (c == ')') || (c == '^') || (c == '*') || (c == '/') || (c == '+') || (c == '-')) {
                                break;
                            }
                            j++;
                        }
                        if (j < s.length()) {
                            int k = j;
                            while ((c == ' ') || (c == '\t') || (c == '\n')) {
                                k++;
                                if (k == s.length()) {
                                    break;
                                }
                                c = s.charAt(k);
                            }
                            if (c == '(') {
                                FuncNode fn = new FuncNode(s.substring(i, j), negate);
                                int b = 1;
                                int kOld = k + 1;
                                while (b != 0) {
                                    k++;
                                    if (k >= s.length()) {
                                        throw new ExpressionParseException("Missing function close bracket.", i + indexErrorOffset);
                                    }
                                    c = s.charAt(k);
                                    if (c == ')') {
                                        b--;
                                    }
                                    else if (c == '(') {
                                        b++;
                                    }
                                    else if ((c == ',') && (b == 1)) {
                                        Expression o = build(s.substring(kOld, k), kOld);
                                        if (o == null) {
                                            throw new ExpressionParseException("Incomplete function.", kOld + indexErrorOffset);
                                        }
                                        fn.add(o);
                                        kOld = k + 1;
                                    }
                                }
                                Expression o = build(s.substring(kOld, k), kOld);
                                if (o == null) {
                                    if (fn.numChildren() > 0) {
                                        throw new ExpressionParseException("Incomplete function.", kOld + indexErrorOffset);
                                    }
                                }
                                else {
                                    fn.add(o);
                                }
                                s1.push(fn);
                                i = k;
                            }
                            else {
                                s1.push(new VarNode(s.substring(i, j), negate));
                                i = k - 1;
                            }
                        }
                        else {
                            s1.push(new VarNode(s.substring(i, j), negate));
                            i = j - 1;
                        }
                        negate = false;
                        term = false;
                        signed = false;
                    }
                    else {
                        throw new ExpressionParseException("Unexpected character: " + String.valueOf(c), i + indexErrorOffset);
                    }
                }
                else if (c == ')') {
                    Stack s3 = new Stack();
                    Stack s4 = new Stack();
                    for (;;) {
                        if (s2.isEmpty()) {
                            throw new ExpressionParseException("Missing open bracket.", i + indexErrorOffset);
                        }
                        Object o = s2.pop();
                        if (o.equals("(")) {
                            break;
                        }
                        s3.addToTail(s1.pop());
                        s4.addToTail(o);
                    }
                    s3.addToTail(s1.pop());
                    s1.push(build(s3, s4));
                }
                else if ((c == '^') || (c == '*') || (c == '/') || (c == '+') || (c == '-')) {
                    term = true;
                    s2.push(String.valueOf(c));
                }
                else {
                    throw new ExpressionParseException("Expected operator or close bracket but found: " + String.valueOf(c), i + indexErrorOffset);
                }
            }
        }
        if (s1.size() != s2.size() + 1) {
            throw new ExpressionParseException("Incomplete expression.", indexErrorOffset + s.length());
        }
        return build(s1, s2);
    }

    private static Expression build(Stack s1, Stack s2) {
        Stack s3 = new Stack();
        Stack s4 = new Stack();
        while (!s2.isEmpty()) {
            Object o = s2.removeTail();
            Object o1 = s1.removeTail();
            Object o2 = s1.removeTail();
            if (o.equals("^")) {
                s1.addToTail(new PowNode((Expression)o1, (Expression)o2));
            }
            else {
                s1.addToTail(o2);
                s4.push(o);
                s3.push(o1);
            }
        }
        s3.push(s1.pop());
        while (!s4.isEmpty()) {
            Object o = s4.removeTail();
            Object o1 = s3.removeTail();
            Object o2 = s3.removeTail();
            if (o.equals("*")) {
                s3.addToTail(new MultNode((Expression)o1, (Expression)o2));
            }
            else if (o.equals("/")) {
                s3.addToTail(new DivNode((Expression)o1, (Expression)o2));
            }
            else {
                s3.addToTail(o2);
                s2.push(o);
                s1.push(o1);
            }
        }
        s1.push(s3.pop());
        while (!s2.isEmpty()) {
            Object o = s2.removeTail();
            Object o1 = s1.removeTail();
            Object o2 = s1.removeTail();
            if (o.equals("+")) {
                s1.addToTail(new AddNode((Expression)o1, (Expression)o2));
            } else if (o.equals("-")) {
                s1.addToTail(new SubNode((Expression)o1, (Expression)o2));
            } else {
                throw new ExpressionParseException("Unknown operator: " + o, -1);
            }
        }
        return (Expression)s1.pop();
    }
}
